public class Solution59 {
    int[][] result;
    final int[] direcX=new int[]{1,0,-1,0};
    final int[] direcY=new int[]{0,1,0,-1};

    public void travel(int tmpX,int tmpY,int lastDirec,int tmpNum){
        result[tmpY][tmpX]=tmpNum;
        for (int i = 0; i < 4; i++) {
            int tmpDirec=(i+lastDirec)%4;
            int newX=tmpX+direcX[tmpDirec];
            int newY=tmpY+direcY[tmpDirec];
            if((0<=newX&&newX< result[0].length)&&(0<=newY&&newY< result.length)&&(result[newY][newX]==0)){
                travel(newX,newY,tmpDirec,tmpNum+1);
                return;
            }
        }
        return;
    }

    public int[][] generateMatrix(int n) {
        result=new int[n][n];
        travel(0,0,0,1);
        return result;
    }

    public static void main(String[] args) {
        Solution59 s=new Solution59();
        System.out.println(s.generateMatrix(3));
    }
}
